package kyssion.leetcode.num101_150;

import kyssion.leetcode.util.TreeNode;

public class code105_前序遍历和中序遍历构造二叉树 {

    public static void main(String[] args) {
        TreeNode treeNode = new code105_前序遍历和中序遍历构造二叉树().buildTree(
                new int[]{3,9,20,15,7},new int[]{9,3,15,20,7}
        );
        System.out.println();
    }

    private int ps=0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        ps = 0;
        return ans(preorder,inorder,0 ,inorder.length-1);
    }


    TreeNode ans(int[] preorder, int[] inorder, int is, int ie) {
        if (ps >= preorder.length || is < 0 || is > ie) {
            return null;
        }
        TreeNode treeNode = new TreeNode(preorder[ps]);
        int index = is;
        for (int a = is; a <= ie; a++) {
            if (inorder[a] == preorder[ps]) {
                index = a;
                break;
            }
        }
        ps++;
        treeNode.left = ans(preorder, inorder, is, index - 1);
        treeNode.right = ans(preorder, inorder, index + 1, ie);
        return treeNode;
    }
}
